package com.leetcode.sort.basic_sort;

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/9/11 11:21
 */
public class OutSort extends Sort {

    public static void sort(File inputFile, File outputFile, File directory) throws IOException {
        Scanner scanner = new Scanner(inputFile);
        PriorityQueue<Integer> big = new PriorityQueue<>(100);
        PriorityQueue<Integer> small = new PriorityQueue<>(100);

        List<Integer> list = new ArrayList<>();

        while (big.size() <= 100 && scanner.hasNext()) {
            big.offer(scanner.nextInt());
        }

        int index = 0;
        while (scanner.hasNext()) {
            int max = Integer.MIN_VALUE;
            File file = File.createTempFile("sorted-list-", index + "", directory);
            PrintWriter writer = new PrintWriter(file);
            while (small.size() <= 100) {
                if (max < big.peek()) {
                    int num = big.poll();
                    max = num;
                    writer.write(num + " ");
                }
            }
        }


    }


    public void sort(int[] nums, int limit) {
        List<Integer[]> sorteds = new ArrayList<>();

        int i = 0;

        Queue<Integer> queue = new PriorityQueue<>();

        while (i < nums.length) {
            if (queue.size() < limit) {
                queue.offer(nums[i]);
            } else {
                sorteds.add(queue.toArray(new Integer[0]));
                queue.clear();
            }
        }

        if (!queue.isEmpty()) {
            sorteds.add(queue.toArray(new Integer[0]));
            queue = null;
        }

        int[] loser = buildLoserTree(sorteds);

    }

    private int[] buildLoserTree(List<Integer[]> sorteds) {
        int size = sorteds.size();
        int[] loser = new int[size + 1];
        loser[size] = Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) {
            loser[i] = sorteds.get(i).length;
        }

        for (int i = 0; i < size; i++) {
            adjust(i, loser, sorteds);
        }
        
        return loser;
    }

    private void adjust(int s, int[] loser, List<Integer[]> sorteds) {
        int len = loser.length;
        int t = s + (len - s) / 2;
        while (t > 0) {
            if (sorteds.get(s)[0].compareTo(sorteds.get(loser[t])[0]) > 0) {
                // 交换两者的值
                loser[t] ^= s;
                s ^= loser[t];
                loser[t] ^= s;
            }
            t >>= 1; // 得到败者树上一个父节点
        }
        loser[0] = s; // 0记录最终的胜者
    }


}
